Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that\r\neach function can only depend on a few nodes. Biologically motivated constraints further show that functions\r\nfound in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It\r\nturns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem\r\nof detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks\r\nwith unbalanced functions and functions of an average sensitivity less than 23\r\nk, where k is the number of\r\ncontrolling variables for a function. Further, we consider the class of 1-low networks which include unate networks,\r\nlinear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral\r\nlearning algorithms leads to both better time and sample complexity for the detection of controlling nodes\r\ncompared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds\r\non the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved\r\nalgorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.
Loading....